package com.github.yangyishe.p100;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 46. 全排列
 * https://leetcode.cn/problems/permutations/description/?envType=study-plan-v2&envId=top-interview-150
 *
 * 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
 *
 *
 *
 * 示例 1：
 *
 * 输入：nums = [1,2,3]
 * 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 * 示例 2：
 *
 * 输入：nums = [0,1]
 * 输出：[[0,1],[1,0]]
 * 示例 3：
 *
 * 输入：nums = [1]
 * 输出：[[1]]
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 6
 * -10 <= nums[i] <= 10
 * nums 中的所有整数 互不相同
 */
public class Problem46 {
    public static void main(String[] args) {
        int[] nums=new int[]{1,2,3};

        Problem46 problem46 = new Problem46();
        List<List<Integer>> permute = problem46.permute(nums);
        System.out.println(permute);

    }

    /**
     * 思路:
     * 全局回溯问题.
     *
     * 一个map记录是否遍历过相应位置(遍历后需要重置), 一个resultList记录结果
     *
     * @param nums
     * @return
     */
    public List<List<Integer>> permute(int[] nums) {
        visited=new boolean[nums.length];

        iterate(nums,0,new ArrayList<>());

        return resultList;
    }

    private boolean[] visited;

    private List<List<Integer>> resultList=new ArrayList<>();

    private void iterate(int[] nums, int numIndex, ArrayList<Integer> tmp){
        if(nums.length==numIndex){
            resultList.add(new ArrayList<>(tmp));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(!visited[i]){
                visited[i]=true;
                if(tmp.size()==i){
                    tmp.add(nums[numIndex]);
                }else{
                    tmp.set(i,nums[numIndex]);
                }
                iterate(nums,numIndex+1,tmp);
                tmp.set(i,null);
                visited[i]=false;
            }
        }
    }

}
